#include "2-bit_tree.hpp"

template<class T = int>
BitNode<T>* insertNodeSTr(BitNode<T>* tree, T data)
{
  if (tree == nullptr) {
    return new BitNode<T>(data);
  }

  if (data < tree->data) {
    tree->lchild = insertNodeSTr(tree->lchild, data);
    tree->lchild->parent = tree;
  }
  if (data > tree->data) {
    tree->rchild = insertNodeSTr(tree->rchild, data);
    tree->rchild->parent = tree;
  }
  return tree;
}

template<class T = int>
BitNode<T>* searchNodeSTr(BitNode<T>* tree, T data)
{
  if (tree == nullptr) {
    return nullptr;
  }

  if (tree->data == data) {
    return tree;
  } else if (data < tree->data ) {
    return searchNodeSTr(tree->lchild, data);
  } else {
    return searchNodeSTr(tree->rchild, data);
  }
}

template<class T = int>
BitNode<T>* delNodeSTr(BitNode<T>* tree)
{
  if (tree == nullptr) {
    return nullptr;
  }
  auto father = tree->parent;

  BitNode<T>* new_tree = nullptr;
  if (tree->lchild == nullptr) {
    new_tree = tree->rchild;
  } else if (tree->rchild == nullptr) {
    new_tree = tree->lchild;
  } else {
    // 查找删除节点的最小右分支节点
    BitNode<T>* rmin_fd = tree;
    BitNode<T>* rmin = tree->rchild;
    while (rmin->lchild != nullptr) {
      rmin_fd = rmin;
      rmin = rmin->lchild;
    }

    // 使用rmin接管tree的左孩子
    rmin->lchild = tree->lchild;
    if (tree->lchild) {
      tree->lchild->parent = rmin;
    }

    if (rmin != tree->rchild) {
      // 当rmin非tree的右孩子时，需rmin_fd接管其右孩子为左孩子
      rmin_fd->lchild = rmin->rchild;
      if (rmin->rchild) {
        rmin->rchild->parent = rmin_fd;
      }

      // 前面已经判断，此处tree节点的右孩子不为空
      rmin->rchild = tree->rchild;
      tree->rchild->parent = rmin;
    }
    new_tree = rmin;
  }

  free(tree);
  // 删除节点设置新节点的父节点
  if (new_tree != nullptr) {
    new_tree->parent = father;
  }
  return new_tree;
}

template<class T = int>
BitNode<T>* delNodeSTr(BitNode<T>* tree, int data)
{
  if (tree == nullptr) {
    return nullptr;
  }

  if (data == tree->data) {
    // 删除节点后可能返回空
    return delNodeSTr(tree);
  }

  if (data < tree->data) {
    tree->lchild = delNodeSTr(tree->lchild, data);
  }
  if (data > tree->data) {
    tree->rchild = delNodeSTr(tree->rchild, data);
  }
  return tree;
}

template<class T = int>
class BitSortTree : public BitTree<T> {
  public:
    BitSortTree() = default;
    explicit BitSortTree(BitNode<T>* _tree) : BitTree<T>(_tree) {}
    virtual ~BitSortTree() = default;
    
    virtual void insertNode(T data) { BitTree<T>::tree = insertNodeSTr(BitTree<T>::tree, data); }
    BitNode<T>* searchNode(T data) { return searchNodeSTr(BitTree<T>::tree, data); }
    virtual void delNode(T data) { BitTree<T>::tree = delNodeSTr(BitTree<T>::tree, data); }
};

